class Solution(object):
    def latestDayToCross(self, row, col, cells):
        p = [i for i in range(row * col)]
        grid = [[1 for _ in range(col)] for _ in range(row)]
        state = [0] * row * col
        rank = [0] * row * col
        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rx = find(x)
            ry = find(y)
            if rx != ry:
                if rx > ry:
                    p[rx] = ry
                    rank[rx] += rank[ry]
                    rank[ry] = 0
                else:
                    p[ry] = rx
                    rank[ry] += rank[rx]
                    rank[rx] = 0
                if state[rx] + state[ry] == 3:
                    return 3
                else:
                    if state[rx] == 1 or state[ry] == 1:
                        state[rx] = 1
                        state[ry] = 1
                    else:
                        if state[rx] == 2 or state[ry] == 2:
                            state[rx] = 2
                            state[ry] = 2
                    return state[rx]

        for index in range(row * col - 1, -1, -1):
            x, y = cells[index]
            x, y = x - 1, y - 1
            grid[x][y] = 0
            if x == 0:
                state[x * col + y] = 1
            if x == row - 1:
                state[x * col + y] = 2
            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= ux < row and 0 <= uy < col and grid[ux][uy] == 0:
                    val = union(ux * col + uy, x * col + y)
                    if val == 3:
                        return index 
            
                    



                

data = Solution()
row = 2
col = 2
cells = [[1,1],[2,1],[1,2],[2,2]]
print(data.latestDayToCross(row, col, cells))